class Algorithm(object):
    """
    需要掌握的算法知识
    基础算法：排序算法（冒泡排序、选择排序、插入排序等）、查找算法（线性查找、二分查找）。
    数据结构：栈、队列、链表、树（二叉树、AVL树等）、图的基本操作和遍历方法。
    图论算法：最短路径问题（Dijkstra、Floyd算法）、最小生成树（Prim、Kruskal算法）。
    动态规划：熟悉常见的动态规划问题模型，如背包问题、最长公共子序列、最长递增子序列等。
    贪心算法：能够识别并解决典型的贪心问题，如霍夫曼编码、最小生成树等。
    搜索算法：深度优先搜索（DFS）、广度优先搜索（BFS）、回溯搜索等。
    数论和组合数学：快速幂、质数筛选、组合数计算等。
    """

    # 快速幂算法模板：
    def quick_pow(self, base, power):
        result = 1
        while power > 0:
            if power % 2 == 1:
                result = result * base
            base = base * base
            power //= 2
        return result

    # 二分查找模板：
    def binary_search(self, arr, target):
        left, right = 0, len(arr) - 1
        while left <= right:
            mid = (left + right) // 2
            if arr[mid] == target:
                return mid
            elif arr[mid] < target:
                left = mid + 1
            else:
                right = mid - 1
        return -1

    # 动态规划背包问题模板：
    def knapsack(self, weights, values, capacity):
        n = len(values)
        dp = [[0] * (capacity + 1) for _ in range(n + 1)]
        for i in range(1, n + 1):
            for w in range(1, capacity + 1):
                if weights[i - 1] <= w:
                    dp[i][w] = max(dp[i - 1][w], dp[i - 1][w - weights[i - 1]] + values[i - 1])
                else:
                    dp[i][w] = dp[i - 1][w]
        return dp[n][capacity]

    # 归并排序模板：
    def merge_sort(self, arr):
        if len(arr) <= 1:
            return arr
        mid = len(arr) // 2
        left = merge_sort(self, arr[:mid])
        right = merge_sort(self, arr[mid:])
        return merge(self, left, right)

    def merge(self, left, right):
        result = []
        i = j = 0
        while i < len(left) and j < len(right):
            if left[i] < right[j]:
                result.append(left[i])
                i += 1
            else:
                result.append(right[j])
                j += 1
        result.extend(left[i:])
        result.extend(right[j:])
        return result

    # 深度优先搜索(DFS)
    def dfs(self, graph, start, visited=None):
        if visited is None:
            visited = set()
        visited.add(start)
        for neighbor in graph[start]:
            if neighbor not in visited:
                dfs(self, graph, neighbor, visited)

    # 广度优先搜索(BFS)
from collections import deque
    def bfs(self, graph, start):
        visited = set()
        queue = deque([start])
        while queue:
            vertex = queue.popleft()
            if vertex not in visited:
                visited.add(vertex)
                for neighbor in graph[vertex]:
                    if neighbor not in visited:
                        queue.append(neighbor)


    # 最小生成树(Prim算法)

    def prim(self, graph, start):
        mst = []
        visited = set([start])
        edges = [(cost, start, to) for to, cost in graph[start].items()]
        while edges:
            cost, frm, to = heapq.heappop(edges)
            if to not in visited:
                visited.add(to)
                mst.append((frm, to, cost))
                for to_next, cost in graph[to].items():
                    if to_next not in visited:
                        heapq.heappush(edges, (cost, to, to_next))
        return mst

    # Dijkstra最短路径算法模板：

    import heapq

    def dijkstra(self, graph, start):
        distances = {vertex: float('infinity') for vertex in graph}
        distances[start] = 0
        priority_queue = [(0, start)]
        while priority_queue:
            current_distance, current_vertex = heapq.heappop(priority_queue)
            if current_distance > distances[current_vertex]:
                continue
            for neighbor, weight in graph[current_vertex].items():
                distance = current_distance + weight
                if distance < distances[neighbor]:
                    distances[neighbor] = distance
                    heapq.heappush(priority_queue, (distance, neighbor))
        return distances

    # 回溯算法解决组合问题模板：

    '''
    def backtrack(self, 路径, 选择列表):
        if 没有更多选择:
            结果.add(路径)
            return
        for 选择 in 选择列表:
            做选择
            backtrack(路径, 选择列表 - {选择})
            撤销选择
    '''

    # 二叉树的前序遍历模板：

    class TreeNode:
        def __init__(self, val=0, left=None, right=None):
            self.val = val
            self.left = left
            self.right = right

    def preorder_traversal(self, root):
        result = []
        if root:
            result.append(root.val)
            result.extend(preorder_traversal(root.left))
            result.extend(preorder_traversal(root.right))
        return result

    #  斐波那契数列模板：
    def fibonacci(self, n):
        a, b = 0, 1
        for _ in range(n):
            a, b = b, a + b
        return a

    # 杨辉三角模板：

    def Pascals_Triangle(self, n):
        triangle = [[1]]
        for i in range(1, n):
            row = [1]
            last_row = triangle[-1]
            for j in range(1, i):
                row.append(last_row[j-1] + last_row[j])
            row.append(1)
            triangle.append(row)
        return triangle

    # 质数生成模板（埃拉托斯特尼筛法）：
    def sieve_of_eratosthenes(self, n):
        prime = [True for i in range(n+1)]
        p = 2
        while (p * p <= n):
            if (prime[p] == True):
                for i in range(p * p, n+1, p):
                    prime[i] = False
            p += 1
        primes = []
        for p in range(2, n+1):
            if prime[p]:
                primes.append(p)
        return primes

    #  字符串匹配模板（KMP算法）：

    def compute_lps_array(self, pattern, M, lps):
        length = 0 # length of the previous longest prefix suffix
        lps[0] = 0 # lps[0] is always 0
        i = 1

        while i < M:
            if pattern[i] == pattern[length]:
                length += 1
                lps[i] = length
                i += 1
            else:
                if length != 0:
                    length = lps[length-1]
                else:
                    lps[i] = 0
                    i += 1

    def KMPSearch(self, pat, txt):
        M = len(pat)
        N = len(txt)

        lps = [0] * M
        compute_lps_array(pat, M, lps)

        i = 0 # index for txt[]
        j = 0 # index for pat[]
        result = []

        while i < N:
            if pat[j] == txt[i]:
                i += 1
                j += 1
            if j == M:
                result.append(i-j)
                j = lps[j-1]
            elif i < N and pat[j] != txt[i]:
                if j != 0:
                    j = lps[j-1]
                else:
                    i += 1

        return result

    #  并查集模板：
    class UnionFind:
        def __init__(self, n):
            self.parent = list(range(n))

        def find(self, x):
            if self.parent[x] != x:
                self.parent[x] = self.find(self.parent[x])
            return self.parent[x]

        def union(self, x, y):
            root_x = self.find(x)
            root_y = self.find(y)
            if root_x != root_y:
                self.parent[root_y] = root_x

        def is_connected(self, x, y):
            return self.find(x) == self.find(y)